package com.sheng.leetcode.year2022.month07.day22;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/07/22
 *
 * 757. 设置交集大小至少为2
 *
 * 一个整数区间 [a, b]  ( a < b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。
 * 给你一组整数区间intervals，请找到一个最小的集合 S，使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。
 * 输出这个最小集合S的大小。
 *
 * 示例 1:
 * 输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
 * 输出: 3
 * 解释:
 * 考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。
 * 且这是S最小的情况，故我们输出3。
 *
 * 示例 2:
 * 输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
 * 输出: 5
 * 解释:
 * 最小的集合S = {1, 2, 3, 4, 5}.
 * 注意:
 *
 * intervals 的长度范围为[1, 3000]。
 * intervals[i] 长度为 2，分别代表左、右边界。
 * intervals[i][j] 的值是 [0, 10^8]范围内的整数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/set-intersection-size-at-least-two
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0757 {

    @Test
    public void test01() {
        //排序[1, 4], [2, 5]，4 - 2 +1 = 3，求出交集的长度，然后
//        int[][] intervals = {{1, 3}, {1, 4}, {2, 5}, {3, 5}};
        int[][] intervals = {{1, 2}, {2, 3}, {2, 4}, {4, 5}};
        System.out.println(new Solution().intersectionSizeTwo(intervals));
    }

}
class Solution {
    /**
     * https://blog.csdn.net/qq_44808827/article/details/119759397
     */
    public int intersectionSizeTwo(int[][] intervals) {
        //排序
        Arrays.parallelSort(intervals, (arr1, arr2) -> arr1[0] == arr2[0] ? arr2[1] - arr1[1] : arr1[0] - arr2[0]);

        int length = intervals.length;
        int ans = 0;
        //初始化为区间元素需要的个数，赋值为2
        //nums[length]表示的是整数区间都至少有nums[length]个元素相交,初始值为2
        int[] nums = new int[length];
        Arrays.fill(nums, 2);

        //从后往前遍历intervals中的元素
        while(--length >= 0) {
            //若第n个区间还需要找到nums[length]个交点 从第n个区间依次取前nums[length]个值 记为val
            //获取数组的第一个值(整数区间的头)
            int left = intervals[length][0];
            //sum为本应添加的交集的数量
            int sum = nums[length];
            for(int i = left; i < left + sum; i++) {
                //更新nz之前的nums数组；
                for(int j = 0 ; j <= length; j++) {
                    //如果nums[j]值大于0，并且所取的val值小于等于intervals中元素的右区间
                    if(nums[j] > 0 && i <= intervals[j][1]) {
                        //更新nums数组
                        nums[j]--;
                    }
                }
                ans++;
            }
        }
        return ans;
    }
//    public int intersectionSizeTwo(int[][] intervals) {
//        if (intervals.length == 1) {
//            return 2;
//        }
//        //排序
//        Arrays.parallelSort(intervals, (arr1, arr2) -> arr1[0] == arr2[0] ? arr2[1] - arr1[1] : arr1[0] - arr2[0]);
//        //交集
//        List<List<Integer>> list = new ArrayList<>();
//        for (int i = 1; i < intervals.length; i++) {
//            //循环整数区间，对当前区间和上一个区间求交集
////            for (int j = intervals[i][0]; j <= intervals[i][1]; j++) {
////                if (i == 1) {
////                    //如果i==1，需要将第一个数组和第二个数组最少两个元素的交集放入集合中
////                }
////            }
//            List<Integer> ccc = ccc(intervals[i - 1], intervals[i]);
//            list.add(ccc);
//        }
//        //去重求并集
//        Set<Integer> integers = new HashSet<>();
//        for (List<Integer> integerList : list) {
//            integers.addAll(integerList);
//        }
//        return integers.size();
//    }
//
//    public List<Integer> ccc(int[] arr1, int[] arr2) {
//        List<Integer> list = new ArrayList<>();
//        int start1 = arr1[0], start2 = arr2[1];
//        int end1 = arr1[1], end2 = arr2[1];
//        //代表分别从arr1和arr2中取出的数的数量，等于2代表满足条件
//        int index1 = 0, index2 = 0;
//        int[] ints1 = new int[arr1[1] - arr1[0] + 1];
//        for (int i = arr1[0]; i <= arr1[1]; i++) {
//            ints1[index1++] = i;
//        }
//        int[] ints2 = new int[arr2[1] - arr2[0] + 1];
//        for (int i = arr2[0]; i <= arr2[1]; i++) {
//            ints2[index2++] = i;
//        }
//        int[] intersect = intersect(ints1, ints2);
//        if (intersect.length == 2) {
//            return Arrays.stream(intersect).boxed().collect(Collectors.toList());
//        } else if (intersect.length > 2) {
//            Arrays.sort(intersect);
//            int[] ints = Arrays.copyOfRange(intersect, intersect.length - 2, intersect.length);
//            return Arrays.stream(ints).boxed().collect(Collectors.toList());
//        } else if (intersect.length == 1) {
//            List<Integer> collect = Arrays.stream(intersect).boxed().collect(Collectors.toList());
//            collect.add(arr1[1] - 1);
//            collect.add(arr2[0] + 1);
//            return collect;
//        } else {
//            List<Integer> arrayList = new ArrayList<>();
//            arrayList.add(arr1[1]);
//            arrayList.add(arr1[1] - 1);
//            arrayList.add(arr2[0]);
//            arrayList.add(arr2[0] + 1);
//            return arrayList;
//        }
//    }
//    public int[] intersect(int[] nums1, int[] nums2) {
//        //如果nums1大于nums2时，交换两个数组
//        if (nums1.length > nums2.length) {
//            intersect(nums2, nums1);
//        }
//        //创建一个哈希表
//        Map<Integer,Integer> map = new HashMap<>();
//        //遍历数组nums1中的元素，count表示重复出现的元素的个数的
//        for (int num: nums1) {
//            int count = map.getOrDefault(num, 0) + 1;
//            map.put(num, count);
//        }
//        //创建一个用于存放输出结果的数组
//        int[] intersection = new int[nums1.length];
//        int index = 0;
//        for (int num : nums2) {
//            //得到遍历数组nums1时对应num元素的个数，该num元素和其对应的count存在哈希表中
//            int count = map.getOrDefault(num, 0);
//            if (count > 0) {
//                //如果哈希表中对应元素的个数大于零，则将此时遍历nums2时的num放进创建的intersection数组中
//                intersection[index++] = num;
//                count--;
//                if (count > 0) {
//                    //将num元素对应的个数count进行自减操作后，再放回哈希表中
//                    map.put(num,count);
//                } else {
//                    //如果num对应的个数值小于等于0就将这个数从哈希表中移除
//                    map.remove(num);
//                }
//            }
//        }
//        return Arrays.copyOfRange(intersection, 0, index);
//    }
}

//不要被样例数据误导了，题目要我们求最小点集的数量，并不规定点集 S 是连续段。
//为了方便，我们令 intervals 为 ins。
//当只有一个线段时，我们可以在线段内取任意两点作为 S 成员，而当只有两个线段时，我们可以两个线段重合情况进行决策：
//当两个线段完全不重合时，为满足题意，我们需要从两个线段中各取两个点，此时这四个点都可以任意取；
//当两个线段仅有一个点重合，为满足 S 最小化的题意，我们可以先取重合点，然后再两个线段中各取一个；
//当两个线段有两个及以上的点重合，此时在重合点中任选两个即可。
//不难发现，当出现重合的所有情况中，必然可以归纳某个线段的边缘点上。即不存在两个线段存在重合点，仅发生在两线段的中间部分：
//因此我们可以从边缘点决策进行入手。
//具体的，我们可以按照「右端点从小到大，左端点从大到小」的双关键字排序，然后从前往后处理每个区间，处理过程中不断往 S 中添加元素，
//由于我们已对所有区间排序且从前往后处理，因此我们往 S 中增加元素的过程中必然是单调递增，
//同时在对新的后续区间考虑是否需要往 S 中添加元素来满足题意时，也是与 S 中的最大/次大值（点集中的边缘元素）做比较，
//因此我们可以使用两个变量 a 和 b 分别代指当前集合 S 中的次大值和最大值（a 和 b 初始化为足够小的值 -1），而无需将整个 S 存下来。
//不失一般性的考虑，当我们处理到 ins[i] 时，该如何决策：
//
//若 ins[i][0] > b（当前区间的左端点大于当前点集 S 的最大值），说明 ins[i] 完全不被 S 所覆盖，为满足题意，
//我们要在 ins[i] 中选两个点，此时直观思路是选择 ins[i] 最靠右的两个点（即 ins[i][1] - 1 和 ins[i][1]）；
//
//若 ins[i][0] > a（即当前区间与点集 S 存在一个重合点 b，由于次大值 a 和 最大值 b 不总是相差 1，我们不能写成 ins[i][0] == b），
//此时为了满足 ins[i] 至少被 2 个点覆盖，我们需要在 ins[i] 中额外选择一个点，此时直观思路是选择 ins[i] 最靠右的点（即ins[i][1]）；
//
//其余情况，说明当前区间 ins[i] 与点集 S 至少存在两个点 a 和 b，此时无须额外引入其余点来覆盖 ins[i]。
//上述情况是对「右端点从小到大」的必要性说明，而「左端点从大到小」目的是为了方便我们处理边界情况而引入的：
//若在右端点相同的情况下，如果「左端点从小到大」处理的话，会有重复的边缘点被加入 S。
//
//上述决策存在直观判断，需要证明不存在比该做法取得的点集 S 更小的合法解：
//
//若存在更小的合法集合方案 A（最优解），根据我们最前面对两个线段的重合分析知道，由于存在任意选点均能满足覆盖要求的情况，因此最优解 A 的具体方案可能并不唯一。
//因此首先我们先在不影响 A 的集合大小的前提下，对具体方案 A 中的非关键点（即那些被选择，但既不是某个具体区间的边缘点，也不是边缘点的相邻点）进行调整（修改为区间边缘点或边缘点的相邻点）。
//这样我们能够得到一个唯一的最优解具体方案，该方案既能取到最小点集大小，同时与贪心解 S 的选点有较大重合度。
//此时如果贪心解并不是最优解的话，意味着贪心解中存在某些不必要的点（可去掉，同时不会影响覆盖要求）。
//然后我们在回顾下，我们什么情况下会往 S 中进行加点，根据上述「不失一般性」的分析：
//当 ins[i][0] > b 时，我们会往 S 中添加两个点，若这个不必要的点是在这个分支中被添加的话，
//意味着当前 ins[i] 可以不在此时被覆盖，而在后续其他区间 ins[j] 被覆盖时被同步覆盖（其中 j > i），
//此时必然对应了我们重合分析中的后两种情况，可以将原本在 ins[j] 中被选择的点，
//调整为 ins[i] 的两个边缘点，结果不会变差（覆盖情况不变，点数不会变多）：
//即此时原本在最优解 A 中不存在，在贪心解 S 中存在的「不必要点」会变成「必要点」。
//当 ins[i] > a 时，我们会往 S 中添加一个点，若这个不必要的点是在这个分支被添加的话，
//分析方式同理，且情况 1 不会发生，如果 ins[i] 和 ins[j] 只有一个重合点的话，起始 ins[i][1] 不会是不必要点：
//
//综上，我们可以经过两步的“调整”，将贪心解变为最优解：第一步调整是在最优解的任意具体方案 A 中发生，通过将所有非边缘点调整为边缘点，
//来得到一个唯一的最优解具体方案；然后通过反证法证明，贪心解 S 中并不存在所谓的可去掉的「不必要点」，
//从而证明「贪心解大小必然不会大于最优解的大小」，即 S > A 不成立，S≤A 恒成立，再结合 A 是最优解的前提（A≤S），可得 S = A。
//
//class Solution {
//    public int intersectionSizeTwo(int[][] ins) {
//        Arrays.sort(ins, (a, b)->{
//            return a[1] != b[1] ? a[1] - b[1] : b[0] - a[0];
//        });
//        int a = -1, b = -1, ans = 0;
//        for (int[] i : ins) {
//            if (i[0] > b) {
//                a = i[1] - 1; b = i[1];
//                ans += 2;
//            } else if (i[0] > a) {
//                a = b; b = i[1];
//                ans++;
//            }
//        }
//        return ans;
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/set-intersection-size-at-least-two/solution/by-ac_oier-3xn6/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
